package com.shuang.backtracking5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class CombinationSum2 {

    //使用标记数组进行去重 树层的选取需要去重 一条树枝下的选取是可以重复的

    //全局变量
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        //定义标记数组 用来记录是否选取过该位置的元素 选过为true
        boolean[] used = new boolean[candidates.length];
        Arrays.fill(used, false);

        //将给的数组进行排序 将重复的元素放在一起 也是为了剪枝优化
        Arrays.sort(candidates);

        //处理
        backTracking(candidates, target, 0, 0, used);

        return res;
    }

    private void backTracking(int[] candidates, int target, int sum, int startIndex, boolean[] used){

        //终止条件(下面循环会做剪枝sum>target的话不会进入递归)
        if (sum == target){
            res.add(new ArrayList(path));
            return;
        }

        //循环
        for (int i = startIndex; i < candidates.length; i++){
            //sum > target 直接跳出循环不进入递归
            if (sum > target){
                break;
            }

            //去重操作 去除树层重复选取相同数字
            //candidates[i] == candidates[i - 1]的情况下：
            // 1. used[i - 1] == true，说明同一树枝candidates[i - 1]使用过 可以
            // 2. used[i - 1] == false，说明同一树层candidates[i - 1]使用过 去重
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]){
                continue;
            }

            //逻辑处理
            sum += candidates[i];
            used[i] = true;
            path.add(candidates[i]);
            //递归
            backTracking(candidates, target, sum, i + 1, used);// 每个节点仅能选择一次，所以从下一位(i + 1)开始
            //回溯
            sum -= candidates[i];
            used[i] = false;
            path.removeLast();
        }
    }

}
